public class CirDoubleList<T>
{
    private DoubleNode<T> head;//头
    private int size;//循环双向链表大小

    public CirDoubleList()//初始化循环双向链表
    {
        head = new DoubleNode<>(null);
        head.setNext(head);
        head.setPrev(head);
        size = 0;
    }

    public boolean isEmpty()////判断是否空
    {
        return size == 0;
    }

    public int size()//返回元素个数（长度）
    {
        return size;
    }

    public String toString()//所有元素的描述字符串
    {
        StringBuilder sb = new StringBuilder();
        DoubleNode<T> current = head.getNext();
        while (current != head)
        {
            sb.append(current.getData()).append(" ");
            current = current.getNext();
        }
        return sb.toString();
    }

    public String toPreviousString()//所有元素的逆序描述字符串
    {
        StringBuilder sb = new StringBuilder();
        DoubleNode<T> current = head.getPrev();
        while (current != head)
        {
            sb.append(current.getData()).append(" ");
            current = current.getPrev();
        }
        return sb.toString();
    }

    public DoubleNode<T> search(T key)//查找并返回与key相等元素
    {
        DoubleNode<T> current = head.getNext();
        while (current != head)
        {
            if (current.getData().equals(key))
            {
                return current;
            }
            current = current.getNext();
        }
        return null;
    }

    public T remove(T key)//查找并删除与key相等元素
    {
        DoubleNode<T> node = search(key);
        if (node == null)
        {
            return null;
        }
        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());
        size--;
        return node.getData();
    }

    public T remove(int i)//查找并删除第i个元素
    {
        if (i < 0 || i >= size)
        {
            return null;
        }
        DoubleNode<T> current = head.getNext();
        for (int j = 0; j < i; j++)
        {
            current = current.getNext();
        }
        current.getPrev().setNext(current.getNext());
        current.getNext().setPrev(current.getPrev());
        size--;
        return current.getData();
    }

    public void clear()//删除所有元素
    {
        head.setNext(head);
        head.setPrev(head);
        size = 0;
    }

    //线性表增加以下方法，参数i表示元素序号，指定操作位置
    public T get(int i)//返回第i个元素数据域的数据
    {
        if (i < 0 || i >= size)
        {
            return null;
        }
        DoubleNode<T> current = head.getNext();
        for (int j = 0; j < i; j++)
        {
            current = current.getNext();
        }
        return current.getData();
    }

    public DoubleNode<T> getDoubleNode(int i)//返回第i个结点对应元素
    {
        if (i < 0 || i >= size)
        {
            return null;
        }
        DoubleNode<T> current = head.getNext();
        for (int j = 0; j < i; j++)
        {
            current = current.getNext();
        }
        return current;
    }

    public void set(int i, T x)//设置第i个元素为x
    {
        if (i < 0 || i >= size)
        {
            return;
        }
        DoubleNode<T> current = head.getNext();
        for (int j = 0; j < i; j++)
        {
            current = current.getNext();
        }
        current.setData(x);
    }

    public int insert(int i, T x)//插入x作为第i个元素
    {
        if (i < 0 || i > size)
        {
            return -1;
        }
        DoubleNode<T> current = head.getNext();
        for (int j = 0; j < i; j++)
        {
            current = current.getNext();
        }
        DoubleNode<T> newNode = new DoubleNode<>(x);
        newNode.setNext(current);
        newNode.setPrev(current.getPrev());
        current.getPrev().setNext(newNode);
        current.setPrev(newNode);
        size++;
        return 0;
    }

    public int insert(T x)//在最后插入x元素
    {
        DoubleNode<T> newNode = new DoubleNode<>(x);
        newNode.setNext(head);
        newNode.setPrev(head.getPrev());
        head.getPrev().setNext(newNode);
        head.setPrev(newNode);
        size++;
        return 0;
    }
}